//一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。 
//
// 现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 10⁹ + 7 取余后再返回。 
//
// 注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。 
//
// 
//
// 示例 1： 
//
// 输入：n = 1
//输出：4
//解释：
//可能的放置方式：
//1. 所有地块都不放置房子。
//2. 一所房子放在街道的某一侧。
//3. 一所房子放在街道的另一侧。
//4. 放置两所房子，街道两侧各放置一所。
// 
//
// 示例 2： 
// 输入：n = 2
//输出：9
//解释：如上图所示，共有 9 种可能的放置方式。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁴ 
// 
//
// Related Topics 动态规划 👍 64 👎 0

package leetcode.editor.cn;
//java:统计放置房子的方式数
public class Q2320CountNumberOfWaysToPlaceHouses {
    public static void main(String[] args){
        Solution solution = new Q2320CountNumberOfWaysToPlaceHouses().new Solution();
        solution.countHousePlacements(1000);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countHousePlacements(int n) {
        if (n == 1) {
            return 4;
        }
        // 打家劫舍，两边街道互相独立，每一边结果相乘就行
        // dp[i] 表示前i个地块的单侧的方式数目
        int[] dp = new int[n + 1];
        dp[1] = 2;// 放置或者不放两种
        dp[2] = 3;// 放置、放1号、2号三种
        int MOD = 1_000_000_007;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }
        return (int) (((long) dp[n] * dp[n]) % MOD);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}